
# 从上到下划分，划分到两个以后，再进行合并


class Solution:

    def sortList(self, head):

        # dummy = ListNode(next=head)

        # cur = head
        # 归并排序
        if not head or not head.next: return head

        slow, fast = head, head.next

        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        
        mid, slow.next = slow.next, None
        left, right = self.sortList(head), self.sortList(mid)
        h = res = ListNode(0)

        while left and right:
            if left.val < right.val:
                h.next = left
                left = left.next
            else:
                h.next = right
                right = right.next
            h = h.next
        
        h.next = left if left else right

        return res.next


